#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"
#include <math.h>

#define MAX_NUM_OF_MACHINE  32
#define MAX_NUM_OF_ROUNDS   10
#define TRUE                1
#define FALSE               0

static int num_of_machine;
static int num_of_rounds;
static int rank;
static int round;

enum Role{
    winner,
    loser,
    bye,
    champion,
    dropout,
    unused
};

struct Round {
    enum Role role;
    int opponent;
};

static struct Round rounds[MAX_NUM_OF_ROUNDS];
static int sense = TRUE;

void init_tournament_barrier_mpi(int numm, int rk)
{
    int i, k, two_k, two_k_1;
    num_of_machine = numm;
    rank = rk;
    i = 1;
    num_of_rounds = 1;
    while (i < num_of_machine) {
        i <<= 1;
        ++num_of_rounds;
    }
#ifdef DEBUG
    printf("machine %d: Initializing...\n", rank);
    printf("machine %d: num_of_rounds %d\n", num_of_rounds);
#endif
    i = rank;
    for (k=0; k<num_of_rounds; ++k) {
        two_k = (1<<k); // 2^k
        two_k_1 = (two_k>>1); // 2^(k-1)
        
        // Start init roles
        if (k == 0)
            // dropout if k = 0
            rounds[k].role = dropout;
        else { // k > 0
            if (i == 0 && two_k >= num_of_machine)
                // champion if k > 0, i = 0, and 2^k >= P
                rounds[k].role = champion;
            else if (i % two_k == two_k_1)
                // loser if k > 0 and i mod 2^k = 2^(k-1)
                rounds[k].role = loser;
            else if (i % two_k == 0) {
                if (i + two_k_1 >= num_of_machine)
                    // bye if k > 0, i mod 2^k = 0, and i + 2^(k-1) >= P
                    rounds[k].role = bye;
                else if (two_k < num_of_machine)
                    // winner if k > 0, i mod 2^k = 0, i + 2^(k-1) < P, and 2^k < P
                    rounds[k].role = winner;
                else rounds[k].role = unused;
            }
            else rounds[k].role = unused;
        }
        if (rounds[k].role == loser)
            rounds[k].opponent = i - two_k_1;
        if (rounds[k].role == winner || rounds[k].role == champion)
            rounds[k].opponent = i + two_k_1;
    }
#ifdef DEBUG
    for (k=0; k<num_of_rounds; ++k) {
        printf("m %d: n %d r: %d\n", rank, k, rounds[k].role);
    }
#endif
}

void tournament_barrier_mpi()
{
    round = 1;
    int recv;
    MPI_Status status;
#ifdef DEBUG
    printf("machine %d, sense %d\n", rank, sense);
#endif
    // arrival
    do {
        switch (rounds[round].role) {
            case loser:
#ifdef DEBUG
                printf("machine %d is loser, it sets opponent %d's flag.\n", rank, rounds[round].opponent);
#endif
                MPI_Send(&sense,
                         1,
                         MPI_INT,
                         rounds[round].opponent,
                         1, 
                         MPI_COMM_WORLD);
#ifdef DEBUG
                printf("machine %d is waiting for opponent %d to sets its sense\n", rank, rounds[round].opponent);
#endif
                MPI_Recv(&recv,
                         1,
                         MPI_INT,
                         rounds[round].opponent,
                         1, 
                         MPI_COMM_WORLD,
                         &status);
                // recv 
#ifdef DEBUG
                printf("machine %d is out of spin\n", rank);
#endif
                goto next;
                break;
            case winner:
#ifdef DEBUG
                printf("machine %d is winner on round %d, spinning\n", rank, round);
#endif
                MPI_Recv(&recv,
                         1,
                         MPI_INT,
                         rounds[round].opponent,
                         1,
                         MPI_COMM_WORLD,
                         &status);
                break;
            case bye:
                // do nothing
                break;
            case champion:
#ifdef DEBUG
                printf("machine %d is champion on round %d, spinning\n", rank, round);
#endif
                MPI_Recv(&recv,
                         1,
                         MPI_INT,
                         rounds[round].opponent,
                         1,
                         MPI_COMM_WORLD,
                         &status);
#ifdef DEBUG
                printf("machine %d is champion on round %d, out of spin and now flip opponent %d's sense\n", rank, round, rounds[round].opponent);
#endif
                MPI_Send(&sense,
                         1,
                         MPI_INT,
                         rounds[round].opponent,
                         1,
                         MPI_COMM_WORLD);
                goto next;
                break;
            default:
                break;
        } // switch
        ++round;
    } while (1);
next:;
}

void release_barrier_mpi()
{
    // wake up
#ifdef DEBUG
    printf("machine %d start waking up others\n", rank);
#endif
    do {
        --round;
        switch (rounds[round].role) {
            case loser: case champion:
                // throw exception
                printf("machine %d: case loser or champion:\n", rank);
                exit(1);
            case bye:
                // do nothing
                break;
            case winner:
#ifdef DEBUG
                printf("machine %d is waking up opponent %d\n", rank, rounds[round].opponent);
#endif
                MPI_Send(&sense,
                         1,
                         MPI_INT,
                         rounds[round].opponent,
                         1,
                         MPI_COMM_WORLD);
                break;
            case dropout:
#ifdef DEBUG
                printf("machine %d is dropout\n", rank);
#endif
                goto out;
            default:
                break;
        } // switch
    } while (1);
out:
    sense = 1 - sense;
}

void mpi_tournament_barrier()
{
    tournament_barrier_mpi();
    release_barrier_mpi();
}

